1593. Elegant
permuted sum
You will be given n integers {a1, a2, …, an}. Find a permutation of these n
integers so that summation of the absolute differences between adjacent
elements is maximized. We will call this value the elegant permuted sum.
Consider the sequence {4, 2,
1, 5}. The permutation {2, 5, 1, 4} yields the maximum summation. For this
permutation sum = |2 – 5| + |5 – 1| +
|1 – 4| = 3 + 4 + 3 = 10. Of all the 24 permutations, you won't get
any summation whose value exceeds 10.
Input. The first line is the number
of test cases t (t < 100). Each case consists of a
line that starts with n (1 <
n < 51) followed by n non-negative integers. None of the elements
of the given permutation will exceed 1000.
Output. For each test case print the
case number followed by the elegant permuted sum.
|
Sample input |
Sample output |
|
3 4
4 2 1 5 4
1 1 1 1 2 10 1 |
Case
1: 10 Case
2: 0 Case 3: 9 |
SOLUTION
greedy
Algorithm analysis
Sort the numbers
of the input sequence a. Create a new
array v, where we’ll construct the
required permutation. Initially put into it the minimum and maximum elements of the sequence a (and, accordingly, remove these
elements from a). We’ll compute the elegant sum
in the variable s. Initialize s = | v[0] – v[1]
|.
As long as a is not empty, choose greedily the best
choice among the following four possibilities:
1.
The smallest element of the current
array a is placed at the start of array v.
2.
The smallest element of the current
array a is placed at the end of array v.
3.
The largest element of the current array a is placed at the start of array v.
4.
The largest element of the current array a is placed at the end of array v.
For each case,
recompute the new
value of s. We make the
choice for which the new value of s will be
the largest. For each test, print the value of s as the answer.
Since a and v are dynamically updated, use deques as containers.
Example
Consider how the algorithm works for the first test case. Sort the array:
a = {1, 2, 4,
5}
Step 1. Push the smallest and the largest elements into array v: v = {1, 5}. Remove these elements from a, whereupon a = {2, 4}.
Append the smallest and the largest elements of array a
to the right and to the left of array
v. The largest value of the sum is reached, for example, on the array {1, 5,
2}.
Step 2. v = {1, 5, 2}, a = {4}. There is one element left in the a
array. Append it to the
right and to the left of array v. Recalculate the
sums.
The resulting sum is 10, it is obtained, for example, for permutation
{4, 1, 5, 2}
Algorithm realization
Declare the deques.
deque<int> a, v;
Read the number of test cases tests.
scanf("%d", &tests);
for (i = 1; i <= tests; i++)
{
Start processing the next test xase. Clear the contents of arrays.
scanf("%d", &n);
a.clear();
v.clear();
Read the input array à.
for (j = 0; j <
n; j++)
{
scanf("%d", &val);
a.push_back(val);
}
Sort the input array.
sort(a.begin(),
a.end());
Push the minimum and
the
maximum elements of the sequence a into array v.
v.push_back(a.back());
v.push_front(a.front());
Initially set s = | v[1] – v[0] |.
s = abs(v.back()
- v.front());
Delete these two
elements from array a.
a.pop_back();
a.pop_front();
While array a is not empty, we consider 4 cases
and make the optimal choice among them using the greedy method.
while (!a.empty())
{
Declare an integer array mx of four
elements.
mx[0] =
abs(v.front() - a.front());
mx[1] =
abs(v.back() - a.front());
mx[2] =
abs(v.front() - a.back());
mx[3] =
abs(v.back() - a.back());
rmax =
*max_element(mx, mx + 4);
if (rmax == mx[0])
{
v.push_front(a.front());
a.pop_front();
} else
if (rmax == mx[1])
{
v.push_back(a.front());
a.pop_front();
} else
if (rmax == mx[2])
{
v.push_front(a.back());
a.pop_back();
} else
{
v.push_back(a.back());
a.pop_back();
}
s += rmax;
}
Print the answer.
printf("Case %d:
%d\n", i, s);
}